// LinePoint.cpp: implementation of the CLinePoint class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "LinePoint.h"
#include "Point.h"
#include <memory.h>

#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif

//////////////////////////////////////////////////////////////////////

const float EPSILON = 1.0e-5f;

//////////////////////////////////////////////////////////////////////

BOOL getCommonRect(RECT *lpCommon, const RECT *lpRect1, const RECT *lpRect2)
{
	int x1 = max(lpRect1->left, lpRect2->left);
	int y1 = max(lpRect1->top, lpRect2->top);
	int x2, y2;
	if (lpRect1->right>=0 && lpRect2->right>=0)
		x2 = min(lpRect1->right, lpRect2->right);
	else
		x2 = max(lpRect1->right, lpRect2->right);
	if (lpRect1->bottom>=0 && lpRect2->bottom>=0)
		y2 = min(lpRect1->bottom, lpRect2->bottom);
	else
		y2 = max(lpRect1->bottom, lpRect2->bottom);
	if ((x2>=0 && x1>x2) || (y2>=0 && y1>y2))
		return FALSE;
	lpCommon->left = x1;
	lpCommon->top = y1;
	lpCommon->right = x2;
	lpCommon->bottom = y2;
	return TRUE;
}

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

BOOL SLinePoint::getMaxRect(RECT *lpRect) const
{
	int x = m_lpPoint[0].x;
	int y = m_lpPoint[0].y;
	int xMin = x;
	int xMax = x;
	int yMin = y;
	int yMax = y;
	for(int i=1; i<m_nPoint; i++) {
		if ((x = m_lpPoint[i].x) < 0)
			continue;
		y = m_lpPoint[i].y;
		xMin = min(xMin, x);
		xMax = max(xMax, x);
		yMin = min(yMin, y);
		yMax = max(yMax, y);
	}
	lpRect->left = xMin;
	lpRect->right = xMax;
	lpRect->top = yMin;
	lpRect->bottom = yMax;
	return TRUE;
}

BOOL SLinePoint::getGivenAngleMaxPoint(SPoint *lpPoint, int dx, int dy) const
{
	if (!m_lpPoint || m_nPoint<=0)
		return FALSE;
	int n;
	int nMaxValue = 0;
	int nMaxIndex = -1;
	for(int i=0; i<m_nPoint; i++) {
		n = dx * m_lpPoint[i].x + dy * m_lpPoint[i].y;
		if (nMaxIndex < 0 || n > nMaxValue) {
			nMaxValue = n;
			nMaxIndex = i;
		}
	}
	if (nMaxIndex < 0)
		return FALSE;
	*lpPoint = m_lpPoint[nMaxIndex];
	return TRUE;
}

BOOL SLinePoint::checkConnected(const SLinePoint *lpLine) const
{
	BOOL fConnected = FALSE;
	for(int i=0; i+1<m_nPoint; i++) {
		const SPoint& pt0 = m_lpPoint[i+0];
		const SPoint& pt1 = m_lpPoint[i+1];
		int xMin = min(pt0.x, pt1.x);
		int xMax = max(pt0.x, pt1.x);
		int yMin = min(pt0.y, pt1.y);
		int yMax = max(pt0.y, pt1.y);
		int dx = pt1.x - pt0.x;
		int dy = pt1.y - pt0.y;
		ASSERT(dx!=0 || dy!=0);
		for(int j=0; j+1<lpLine->m_nPoint; j++) {
			const SPoint& pt_0 = lpLine->m_lpPoint[j+0];
			const SPoint& pt_1 = lpLine->m_lpPoint[j+1];
			if ((pt_0.x<xMin && pt_1.x<xMin) ||
				(pt_0.x>xMax && pt_1.x>xMax) ||
				(pt_0.y<yMin && pt_1.y<yMin) ||
				(pt_0.y>yMax && pt_1.y>yMax))
				continue;
			int n1 = dy * (pt_0.x - pt0.x) - dx * (pt_0.y - pt0.y);
			int n2 = dy * (pt_1.x - pt0.x) - dx * (pt_1.y - pt0.y);
			if ((n1 < 0 && n2 < 0) || (n1 > 0 && n2 > 0))
				continue;
			int m0 = (pt_1.x - pt_0.x) * dy - (pt_1.y - pt_0.y) * dx;
			if (m0 != 0) {
				int m1 = pt_0.x * dy - pt_0.y * dx;
				float t = -m1 / (float)m0;
				if (t<0 || t>1)
					continue;
				float s;
				if (abs(dx) >= dy) {
					float tX = pt_0.x + t * (pt_1.x - pt_0.x);
					s = (tX - pt0.x) / dx;
				} else {
					float tY = pt_0.y + t * (pt_1.y - pt_0.y);
					s = (tY - pt0.y) / dy;
				}
				if (0<=s && s<=1)
				{
					fConnected = TRUE;
					break;
				}
			} else {
				// same direction/angle
				fConnected = TRUE;
				break;
			}
		}
	}
	return fConnected;
}

float SLinePoint::getSumLength(void) const
{
	ASSERT(this != NULL);
	double dfSumLength = 0;
	for(int i=1; i<m_nPoint; i++) {
		int dx = m_lpPoint[i].x - m_lpPoint[i-1].x;
		int dy = m_lpPoint[i].y - m_lpPoint[i-1].y;
		dfSumLength += sqrt((double)(dx * dx + dy * dy));
	}
	return (float)dfSumLength;
}

float SLinePoint::inRect(const RECT *lpRect, const SPoint *lpPt1, const SPoint *lpPt2)
{
	int nXMin = min(lpPt1->x, lpPt2->x);
	int nXMax = max(lpPt1->x, lpPt2->x);
	int nYMin = min(lpPt1->y, lpPt2->y);
	int nYMax = max(lpPt1->y, lpPt2->y);
	// totally out of rectangle
	if (nXMax < lpRect->left || nYMax < lpRect->top ||
		(lpRect->right>=0 && nXMin>=lpRect->right) ||
		(lpRect->bottom>=0 && nYMin>=lpRect->bottom))
		return 0.0f;
	// totally in this rectangle
	if (nXMin>=lpRect->left && nYMin>=lpRect->top &&
		(lpRect->right<0 || nXMax<=lpRect->right) &&
		(lpRect->bottom<0 || nYMax<=lpRect->bottom))
		return 1.0f;
	RECT rCommon;
	rCommon.left = max(nXMin, lpRect->left);
	rCommon.top = max(nYMin, lpRect->top);
	rCommon.right = (lpRect->right>=0 ? min(nXMax, lpRect->right) : nXMax);
	rCommon.bottom = (lpRect->bottom>=0 ? min(nYMax, lpRect->bottom) : nYMax);
	int dx = rCommon.right - rCommon.left;
	int dy = rCommon.bottom - rCommon.top;
	if (dx<=0 && dy<=0)
		return 0;
	if (dx >= dy)
		return dx / (nXMax - nXMin + EPSILON);
	return dy / (nYMax - nYMin + EPSILON);
}

//////////////////////////////////////////////////////////////////////

SLinePointEx::SLinePointEx()
{
	m_lpPoint = NULL;
	m_nPoint = 0;
	m_pfLength = NULL;
	memset(&m_rect, 0, sizeof(RECT));
	m_fLength = 0.0f;
}

SLinePointEx::~SLinePointEx()
{
	if (m_pfLength != NULL) {
		delete[] m_pfLength;
		m_pfLength = NULL;
	}
}

BOOL SLinePointEx::createFrom(const SLinePoint *lpLine)
{
	ASSERT(this != NULL && m_pfLength == NULL);
	ASSERT(lpLine != NULL && lpLine->m_lpPoint != NULL && lpLine->m_nPoint > 0);
	m_lpPoint = lpLine->m_lpPoint;
	m_nPoint = lpLine->m_nPoint;
	lpLine->getMaxRect(&m_rect);
	// to create length
	int dx, dy;
	m_pfLength = new float[m_nPoint-1];
	// to count total length
	m_fLength = 0.0f;
	for(int i=0; i+1<m_nPoint; i++) {
		dx = m_lpPoint[i+1].x - m_lpPoint[i].x;
		dy = m_lpPoint[i+1].y - m_lpPoint[i].y;
		m_pfLength[i] = sqrtf((float)(dx * dx + dy * dy));
		m_fLength += m_pfLength[i];
	}
	return TRUE;
}

BOOL SLinePointEx::getCenter(float *pfX, float *pfY, float *pfWeight) const
{
	if (pfWeight != NULL)
		*pfWeight = 0;
	if (m_nPoint <= 0)
		return FALSE;
	if (m_nPoint == 1)
	{
		*pfX = (float)m_lpPoint[0].x;
		*pfY = (float)m_lpPoint[0].y;
		if (pfWeight != NULL)
			*pfWeight = 1.0f;
		return TRUE;
	}
	float dist;
	float fSumX = 0;
	float fSumY = 0;
	float fCount = 0;
	for(int i=1; i<m_nPoint; i++)
	{
		dist = m_pfLength[i - 1];
		fSumX += (m_lpPoint[i].x + m_lpPoint[i-1].x) * dist;
		fSumY += (m_lpPoint[i].y + m_lpPoint[i-1].y) * dist;
		fCount += dist;
	}
	*pfX = fSumX / max(fCount, 1.0f) * 0.5f;
	*pfY = fSumY / max(fCount, 1.0f) * 0.5f;
	if (pfWeight != NULL)
		*pfWeight = max(fCount, 1.0f);
	return TRUE;
}

float SLinePointEx::getInRectRatio(const RECT *lpRect) const
{
	RECT rCommon;
	if (!getCommonRect(&rCommon, lpRect, &m_rect))
		return 0.0f;
	if (memcmp(&rCommon, &m_rect, sizeof(RECT)) == 0)
		return 1.0f;
	float fInRectRatio, fDist;
	float fSumInRect = 0.0f;
	float fSumOutRect = 0.0f;
	for(int i=1; i<m_nPoint; i++)
	{
		fDist = m_pfLength[i-1];
		fInRectRatio = inRect(lpRect, &m_lpPoint[i-1], &m_lpPoint[i]);
		if (fInRectRatio > EPSILON)
			fSumInRect += fDist * fInRectRatio;
		if (fInRectRatio < 1-EPSILON)
			fSumOutRect += fDist * (1 - fInRectRatio);
	}
	return fSumInRect / max(fSumInRect + fSumOutRect, EPSILON);
}

///////////////////////////////////////////////////////////////////////////////

float SLinePointEx::getLeftXRatio(float fX) const
{
    int dx;//, dy;
	SPoint ptLeft, ptRight;
	getGivenAngleMaxPoint(&ptLeft, -1, 0);
	if (ptLeft.x > fX)
		return 0.0f;
	getGivenAngleMaxPoint(&ptRight, +1, 0);
	if (ptRight.x < fX)
		return 1.0f;
	float f, fDist;
	float fLeft = 0.0f;
	float fRight = 0.0f;
	for(int i=0; i<m_nPoint; i++)
	{
		dx = m_lpPoint[i].x - m_lpPoint[i-1].x;
		//dy = m_lpPoint[i].y - m_lpPoint[i-1].y;
		fDist = m_pfLength[i];
		if (dx == 0)
		{
			if (m_lpPoint[i].x <= fX)
				fLeft += fDist;
			else
				fRight += fDist;
			continue;
		}

		if (m_lpPoint[i-1].x < fX+EPSILON)
		{
			if (m_lpPoint[i].x < fX+EPSILON)
				fLeft += fDist;
			else {
				f = fabsf(fX - m_lpPoint[i-1].x) * fDist / abs(dx);
				fLeft += f;
				fRight += fDist - f;
			}
		}
		else
		{
			if (m_lpPoint[i].x > fX-EPSILON)
				fRight += fDist;
			else {
				f = fabsf(fX - m_lpPoint[i].x) * fDist / abs(dx);
				fLeft += f;
				fRight += fDist - f;
			}
		}
	}
	return fLeft / max(fLeft + fRight, EPSILON);
}

float SLinePointEx::getTopYRatio(float fY) const
{
    int dy;//, dx;
	SPoint ptTop, ptBottom;
	getGivenAngleMaxPoint(&ptTop, 0, -1);
	if (ptTop.y > fY)
		return 0.0f;
	getGivenAngleMaxPoint(&ptBottom, 0, +1);
	if (ptBottom.y < fY)
		return 1.0f;
	float f, fDist;
	float fTop = 0.0f;
	float fBottom = 0.0f;
	for(int i=0; i<m_nPoint; i++)
	{
		//dx = m_lpPoint[i].x - m_lpPoint[i-1].x;
		dy = m_lpPoint[i].y - m_lpPoint[i-1].y;
		fDist = m_pfLength[i];
		if (dy == 0)
		{
			if (m_lpPoint[i].y <= fY)
				fTop += fDist;
			else
				fBottom += fDist;
			continue;
		}

		if (m_lpPoint[i-1].y < fY+EPSILON)
		{
			if (m_lpPoint[i].y < fY+EPSILON)
				fTop += fDist;
			else {
				f = fabsf(fY - m_lpPoint[i-1].y) * fDist / abs(dy);
				fTop += f;
				fBottom += fDist - f;
			}
		}
		else
		{
			if (m_lpPoint[i].y > fY-EPSILON)
				fBottom += fDist;
			else {
				f = fabsf(fY - m_lpPoint[i].y) * fDist / abs(dy);
				fTop += f;
				fBottom += fDist - f;
			}
		}
	}
	return fTop;
}

float SLinePointEx::getCrossXRatio(float fX) const
{
	float fRatio = getLeftXRatio(fX);
	if (fRatio < EPSILON || fRatio > 1 - EPSILON)
		return 0.0f;
	if (fRatio <= 0.5f)
		return fRatio / (1 - fRatio);
	return (1 - fRatio) / fRatio;
}

float SLinePointEx::getCrossYRatio(float fY) const
{
	float fRatio = getTopYRatio(fY);
	if (fRatio < EPSILON || fRatio > 1 - EPSILON)
		return 0.0f;
	if (fRatio <= 0.5f)
		return fRatio / (1 - fRatio);
	return (1 - fRatio) / fRatio;
}

float SLinePointEx::getRatioInRect(const RECT *lpRect) const
{
	float dist, fRatio;
	float fDistInRect = 0.0f;
	float fSumDist = 0.0f;
    //int dx, dy;
    int d1, d2;
	for(int i=1; i<m_nPoint; i++)
	{
		//dx = m_lpPoint[i].x - m_lpPoint[i-1].x;
		//dy = m_lpPoint[i].y - m_lpPoint[i-1].y;
		dist = m_pfLength[i];
		fSumDist += dist;

		if ((m_lpPoint[i-1].y<=lpRect->top && m_lpPoint[i].y<=lpRect->top) ||
			(m_lpPoint[i-1].y>=lpRect->bottom && m_lpPoint[i].y>=lpRect->bottom) ||
			(m_lpPoint[i-1].x<=lpRect->left && m_lpPoint[i].x<=lpRect->left) ||
			(m_lpPoint[i-1].x>=lpRect->right && m_lpPoint[i].x>=lpRect->right))
			continue;

		RECT rCommon;
		RECT r = {min(m_lpPoint[i-1].x, m_lpPoint[i].x), min(m_lpPoint[i-1].y, m_lpPoint[i].y),
			max(m_lpPoint[i-1].x, m_lpPoint[i].x), max(m_lpPoint[i-1].y, m_lpPoint[i].y)};
		if (!getCommonRect(&rCommon, &r, lpRect))
			continue;
		d1 = rCommon.right - rCommon.left + 1;
		d2 = rCommon.bottom - rCommon.top + 1;
		if (d1 >= d2)
			fRatio = d1 / (r.right - r.left + 1.0f);
		else
			fRatio = d2 / (r.bottom - r.top + 1.0f);
		fDistInRect += fRatio * dist;
	}
	return fDistInRect / max(fSumDist, 1.0f);
}
